package main

//选择排序
//选择式排序也属于内部排序法,是从预排序的数据中,按照指定的规则选出某一个元素,经过和其他元素重整,
//再次原则交换位置后达到排序的目的
func SelectSort(arr *[100000]int) {
	for whereIndex := 0; whereIndex < len(arr)-1; whereIndex++ {
		maxIndex := whereIndex
		for i := 1 + whereIndex; i < len(*arr); i++ {
			if arr[maxIndex] < arr[i] {
				maxIndex = i
			}
		}
		if maxIndex != whereIndex {
			arr[maxIndex], arr[whereIndex] = arr[whereIndex], arr[maxIndex]
		}
	}
}

//插入排序
//插入式排序属于内部排序法,是对预排序的元素以插入的方式寻找元素的适当位置,已达到排序的目的
func InsertSort(arr *[1000000]int) {
	for i := 1; i < len(arr); i++ {
		insertVal := arr[i]
		insertIndex := i - 1
		for insertIndex >= 0 && arr[insertIndex] < insertVal {
			arr[insertIndex+1] = arr[insertIndex]
			insertIndex--
		}
		if insertIndex+1 != i {
			arr[insertIndex+1] = insertVal
		}
	}
}

//快速排序  冒泡排序的升级版
// 3, 2, 5, 9, 0, -2, 1
// 快速排序是对冒泡排序的一种改进,
//基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据
//都比另外一部分的所有数据都要小,然后再按照此方法对这两部分数据分别进行快速排序,
//整个过程可以递归进行,以此达到整个数据 变成有序序列
func QuickSort(left int, right int, arr *[10000000]int) {
	l := left
	r := right
	pivot := arr[(left+right)/2]
	for l < r {
		for arr[l] < pivot {
			l++
		}
		for arr[r] > pivot {
			r--
		}
		if l >= r {
			break
		}
		arr[r], arr[l] = arr[l], arr[r]

		if arr[l] == pivot {
			r--
		}
		if arr[r] == pivot {
			l++
		}
	}
	if r == l {
		l++
		r--
	}
	if left < r {
		QuickSort(left, r, arr)
	}
	if right > r {
		QuickSort(l, right, arr)
	}
}

func QuickSort2(left int, right int, arr *[100000000]int) {
	if left < right {
		l := left
		r := right
		pivot := arr[l]
		for l < r {
			for l < r && arr[r] > pivot {
				r--
			}
			if l < r {
				arr[l] = arr[r]
				l++
			}
			for l < r && arr[l] < pivot {
				l++
			}
			if l < r {
				arr[r] = arr[l]
				r--
			}
		}
		arr[l] = pivot
		QuickSort2(left, l-1, arr)
		QuickSort2(l+1, right, arr)
	}
}
